class Solution(object):
    def shortestPath(self, grid, k):
        m = len(grid)
        n = len(grid[0])
        st = {(0, 0, 0)}
        already = {(0, 0): 0}
        dist = 0
        while st:
            dist += 1
            next_st = set()
            for x, y, cost in st:
                for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= ux < m and 0 <= uy < n:
                        if (ux, uy) not in already:
                            if (ux, uy) == (m - 1, n - 1):
                                return dist
                            if grid[ux][uy] == 0:
                                already[(ux, uy)] = cost
                                next_st.add((ux, uy, cost))
                            else:
                                if cost + 1 <= k:
                                    already[(ux, uy)] = cost + 1
                                    next_st.add((ux, uy, cost + 1))
                        else:
                            if grid[ux][uy] == 0:
                                next_cost = cost
                            else:
                                next_cost = cost + 1
                            if next_cost < already[(ux, uy)]:
                                already[(ux, uy)] = next_cost
                                next_st.add((ux, uy, next_cost))
            st = next_st
        return -1





data = Solution()
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]
k = 1
print(data.shortestPath(grid, k))